package com.lw.leetcode.binary.c;

/**
 * Created with IntelliJ IDEA.
 * 862. 和至少为 K 的最短子数组
 *
 * @author liw
 * @version 1.0
 * @date 2022/10/26 10:33
 */
public class ShortestSubarray {

    public static void main(String[] args) {
        ShortestSubarray test = new ShortestSubarray();

        // 1
//        int[] nums = {1};
//        int k = 1;

        // -1
//        int[] nums = {1, 2};
//        int k = 4;

        // 3
//        int[] nums = {2, -1, 2};
//        int k = 3;

        // 7
//        int[] nums = {-53, 81, -96, 66, 56, -5, -45, 8, 42, 33};
//        int k = 123;

        // 2
        int[] nums = {-122, -686, -893, 962, 695, -237, -781, 431, -411, -996, -460, -721, 471, -439, -321, 932, 584, 741, -703, 76, -843, -651, 429, -784, -88, -388, -891, -755, 318, -780, -924, -799, 186, -577, 95, 726, 393, -661, 617, -714, -658, -120, -656, 619, 66, 940, 645, -406, 846, 939, 707, -863, 609, 140, 781, -229, -503, 737, 997, 923};
        int k = 1912;

        //
//        int[] nums = Utils.getArr(100, -1000, 1000);
//        int k = 1912;
//        System.out.println(k);

        int i = test.shortestSubarray(nums, k);
        System.out.println(i);
    }

    public int shortestSubarray(int[] nums, int k) {
        int length = nums.length;
        long[] arr = new long[length + 1];
        int[] items = new int[length + 1];
        items[0] = -1;
        int index = 0;
        long sum = 0;
        int value = Integer.MAX_VALUE;
        for (int i = 0; i < length; i++) {
            sum += nums[i];
            while (index >= 0 && arr[index] >= sum) {
                long v = arr[index] - k + 1;
                if (arr[0] >= v) {
                    index--;
                    continue;
                }
                int t = find(arr, index, v);
                value = Math.min(value, items[index] - items[t]);
                index--;
            }
            index++;
            arr[index] = sum;
            items[index] = i;
//            System.out.println(Arrays.toString(arr));
        }
        while (index >= 0) {
            long v = arr[index] - k + 1;
            if (arr[0] >= v) {
                break;
            }
            int t = find(arr, index, v);
            value = Math.min(value, items[index]  - items[t]);
            index--;
        }
        return value == Integer.MAX_VALUE ? -1 : value;
    }

    private int find(long[] nums, int end, long t) {
        int st = 0;
        while (st < end) {
            int m = st + ((end - st + 1) >> 1);
            if (nums[m] < t) {
                st = m;
            } else {
                end = m - 1;
            }
        }
        return st;
    }

}
